// Package _8_对称的二叉树 main
// @Title _8_对称的二叉树
// @Description  判断一颗二叉树是否是对称的
// @Author  == 琳琳也叫王木木 ==  2022-01-12 19:02
// @Create  2022-01-12 19:02
package main

import (
	"fmt"
)

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

/**
二叉树对称一定有：对于任意两个对称的节点L 和R
- L.Val = R.Val
L.Left.Val = R.Right.Val
L.Right.Val = R.Left.Val
*/

func main() {
	root := TreeNode{
		1,
		&TreeNode{
			2,
			&TreeNode{
				3,
				nil, nil,
			}, &TreeNode{
				4, nil, nil,
			},
		}, &TreeNode{
			2,
			&TreeNode{
				4,
				nil, nil,
			}, &TreeNode{
				3,
				nil, nil,
			},
		},
	}
	fmt.Println(isSymmetric(&root))
}

func isSymmetric(root *TreeNode) bool {
	// 如果根节点为空，返回对称
	if root == nil {
		return true
	}
	return process(root.Left, root.Right)
}

func process(l, r *TreeNode) bool {
	// 左右节点都为空时,说明到底了,匹配成功,返回true
	if l == nil && r == nil {
		return true
	}
	// 有任意一个节点为空 说明不对称 或者两个节点的值不等
	if l == nil || r == nil || l.Val != r.Val {
		return false
	}
	//匹配对称的值  left.val != right.val
	//再去对称匹配子节点 dfs(left.left, right.right) && dfs(left.right, right.left);
	return process(l.Left, r.Right) && process(l.Right, r.Left)
}
